// #include <iostream>
// #include <vector>
// #include <algorithm>
// using namespace std;
// class Solution
// {
// public:
//     void moveZeroes(vector<int>&nums)
//     {
//         // for(int dest=-1,cur=0;cur<nums.size();cur++)
//         //     if(nums[cur])
//         //         swap(nums[++dest],nums[cur]);
//         for(size_t dest=0,i=0;i<nums.size();i++)
//         {
//             if(nums[i])
//             {
//                 swap(nums[dest],nums[i]);
//                 dest++;
//             }
//         }
//     }
// };
// int main()
// {    
//     vector<int> va;
//     va.push_back(0);
//     va.push_back(1);
//     // va.push_back(0);
//     // va.push_back(3);
//     // va.push_back(12);
//     Solution s;
//     s.moveZeroes(va);
//     for(auto e:va)
//     {
//         cout<<e<<" ";
//     }
//     cout<<endl;
//     return 0;
// }

// #include <iostream>
// int main()
// {
//     int a=-10;
//     if(!a)std::cout<<"-10"<<std::endl;
//     if(a)std::cout<<"10"<<std::endl;
//     std::cout<<!a<<std::endl;
//     return 0;
// }

// #include <iostream>
// #include <vector>

// int countWays(int n) {
//     if (n == 1) return 1;
//     if (n == 2) return 2;

//     // 初始化 dp 数组
//     std::vector<int> dp(n + 1, 0);
//     dp[1] = 1;
//     dp[2] = 2;

//     // 填充 dp 数组
//     for (int i = 3; i <= n; ++i) {
//         dp[i] = dp[i - 1] + dp[i - 2];
//     }

//     return dp[n];
// }

// int main() {
//     int n;
//     std::cout << "请输入台阶数: ";
//     std::cin >> n;

//     std::cout << "上 " << n << " 个台阶的方法数为: " << countWays(n) << std::endl;

//     return 0;
// }

// // #include <iostream>
// // using namespace std;
// // int count=0;
// // void prem(int a[],int k,int n)
// // {

// //     if(k==1)
// //     {
// //         for(int i=0;i<n;i++)
// //         {
// //             cout<<a[i]<<" ";
// //         }
// //         count++;
// //         cout<<endl;
// //     }   
// //     else
// //     {
// //         for(int i=n-k;i<n;i++)
// //         {
// //             swap(a[i],a[n-k]);
// //             prem(a,k-1,n);
// //             swap(a[i],a[n-k]);
// //         }
// //     }
// // }
// // int stein(int a,int b)
// // {
// //     if(a==0)return b;
// //     if(b==0)return a;
// //     if(a%2==0&&b%2==0)
// //         return 2*stein(a>>1,b>>1);
// //     else if(a%2==0)
// //         return stein(a>>1,b);
// //     else if(b%2==0)
// //         return stein(a,b>>1);
// //     else
// //         return stein(abs(a-b),min(a,b));
    
// // }
// // void test01()
// // {
// //     int n,k;
// //     cin>>n>>k;
// //     int a[n];
// //     for(int i=0;i<n;i++)
// //     {
// //         cin>>a[i];
// //     }
// //     prem(a,k,n);
// //     cout<<count<<endl;
// // }
// // void test02()
// // {
// //     int m,n;
// //     cin>>m>>n;
// //     cout<<"m和n的最大公约数是"<<stein(m,n)<<endl;
// // }
// // int main()
// // {
// //     // test01();
// //     test02();
// //     return 0;
// // }
// #include <iostream>
// #include <vector>
// using namespace std;
// int main()
// {
//     size_t k;
//     int count=0,n;
//     cin>>k;
//     vector<int> v;
//     while(cin>>n)
//     {
//         if(n==-1)break;
//         v.push_back(n);
//     }
//     if(k>v.size()||k<=0)
//     {
//         cout<<"NULL"<<endl;return 0;
//     }
//     for(auto it=v.rbegin();it!=v.rend();it++)
//     {
//         count++;
//         if(count==k)
//             cout<<*it<<endl;
//     }
//     return 0;
// }

//贪心解决会议室安排问题
// #include <iostream>
// #include <ctime>
// #include <algorithm>
// #include <string>
// using namespace std;
// struct Events
// {
//     int id;
//     long start_time;
//     long end_time;
// };
// bool cmp(Events a,struct Events b)
// {
//     return a.end_time < b.end_time;
// }
// void venue_arragement(int n,Events event[],bool A[])
// {
//     sort(event,event+n,cmp);
//     int j=0,i=1;
//     A[0]=true;
//     while(i<n)
//     {
//         if(event[i].start_time>=event[j].end_time)
//         {
//             A[i]=true;
//             j=i;
//         }
//         else 
//         A[i]=false;
//         i++;        
//     }
// }
// int main()
// {
//     int n;
//     cin>>n;
//     Events events[n];
//     bool a[n];
//     for(int i=0;i<n;i++)
//     {
//         events[i].id=i+1;
//         cin>>events[i].start_time>>events[i].end_time;
//     }
//     venue_arragement(n,events,a);
//     for(int i=0;i<n;i++)
//     {
//         if(a[i])cout<<events[i].id<<" "<<events[i].start_time<<" "<<events[i].end_time<<endl;
//     }
//     return 0;
// }

// #include <iostream>
// #include <cstdlib>
// using namespace std;
// struct Object
// {
//     void *operator new(size_t i)
//     {
//         void* p=malloc(sizeof(int)*i);
//         if(!p)cout<<"operator new fail"<<endl;
//         else cout<<"operator new success"<<endl;     
//         return p;       
//     }
//     void operator delete(void* ptr)
//     {
//         if(!ptr)cout<<"ptr is null"<<endl;
//         if(ptr)
//         {free(ptr);cout<<"nnnn"<<endl;}
//     }
//     int data[10];
    
// };
// int main()
// {
//     Object* obj2;
//     obj2=new Object;
//     if(!obj2)cout<<"obj2 operator new fail"<<endl;
//     Object* obj3=nullptr;
//     obj2->operator delete(obj2);
//     cout<<"oooooooo"<<endl;
//     obj3->operator delete(obj3);
//     cout<<endl;
//     return 0;
// }

// #include <iostream>
// #include <algorithm>
// #include <vector>
// #include <functional>
// using namespace std;
// bool com(int a,int b){return a>b;}
// class Solution {
// public:
//     int maxArea(vector<int>& height) {
//         vector<int> v;//存储最大水的容量
//         int left=0,right=height.size()-1;
//         while(left!=right)
//         {
//             v.push_back(min(height[left],height[right])*(right-left));
//             if(height[left]<height[right])left++;
//             else right--;
//         }
//         sort(v.begin(),v.end(),com);
//         //sort(v.begin(),v.end(),greater<int>());两种都可以，需要包含functional的头文件
//         return v[0];
//     }
// };
// int main()
// {
//     Solution s;
//     vector<int> x;
//     x.push_back(1);
//     x.push_back(8);
//     x.push_back(6);
//     x.push_back(2);
//     x.push_back(5);
//     x.push_back(4);
//     x.push_back(3);
//     x.push_back(8);
//     x.push_back(7);
//     cout<<s.maxArea(x);
//     return 0;
// }
// #include <iostream>
// #include <algorithm>
// #include <cfloat>
// #define INF DBL_MAX
// #define N 5

// int main()
// {
//     return 0;
// }
// #include <iostream>
// #include <string>
// using namespace std;
// int main() 
// {
//     int T,n,k;
//     int wincount=0,starnumber=0;
//     cin>>T;
//     while(T)
//     {
//         wincount=0,starnumber=0;
//         cin>>n>>k;
//         string s1;
//         cin>>s1;
//         for(int i=0;i<s1.size();i++)
//         {
//             if(s1[i]=='W')
//             {
//                 ++wincount;
//                 if(wincount<3)starnumber++;
//                 if(wincount>=3)
//                 {
//                     starnumber+=k;
//                     wincount++;
//                 }
//             }
//             if(s1[i]=='L')
//             {
//                 starnumber--;
//                 if(wincount>=3)wincount=0;
//             }
//         }
//         cout<<starnumber<<endl;
//         T--;
//     }
//     return 0;
// }

// #include <iostream>
// #include <windows.h>

// int main()
// {
//     int i=10;
//     // std::cout<<"hello";
//     //fflush(stdout);
//     while(i--)
//     {
//         std::cout<<i<<"\r";
//         fflush(stdout);
//         Sleep(1000);
//     }
//     std::cout<<std::endl;
//     return 0;
// }


// #include <iostream>
// #include <string>
// #include <vector>
// using namespace std;
// bool Getchar(char s)
// {
//     if(s>='a'&&s<='z')return true;
//     if(s>='A'&&s<='Z')return true;
//     return false;
// }
// class Solution {
// public:
//     /**
//      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//      *
//      * 
//      * @param str string字符串 原串
//      * @param arg char字符型vector 需替换数组
//      * @return string字符串
//      */
//     string formatString(string str, vector<char>& arg) {
//         // write code here
//         size_t vectorsize=arg.size();
//         size_t strsize=str.size();
//         int j=0;
//         for(size_t i=0;i<str.size();i++)
//         {
//             if(!Getchar(str[i]))
//             {
//                 if(str[i]=='%')
//                 {
//                     for(size_t k=i;k<str.size();k++)
//                     {
//                         str[k]=str[k+1];
//                     }
//                     str.resize(strsize--);
//                 }
//                 str[i]=arg[j++];
//                 --vectorsize;
//             }
//         }
//         if(vectorsize!=0)
//         for(size_t i=j;j<=arg.size();i++)
//         {
//             // str.insert(str.end()-1,arg[i]);
//             str+=arg[i];
//         }
//         return str;
//     }
// };
// int main()
// {
//     Solution s2;
//     string s("A\%sC\%sE");
//     vector<char> v;
//     v.push_back('B');
//     v.push_back('D');
//     v.push_back('F');
//     auto ss=s2.formatString(s,v);
//     for(auto e:ss)
//     {
//         cout<<e<<" ";
//     }
//     cout<<endl;
//     return 0;
// }

// #include <iostream>
// #include <vector>
// using namespace std;
// #include <algorithm>
// class Solution 
// {
// public:
//     vector<vector<int>> threeSum(vector<int>& nums) 
//     {
//         vector<vector<int>> retvector;
//         sort(nums.begin(),nums.end());
//         for(size_t i=0;i<nums.size()-2;i++)
//         {
//             if(i>0&&nums[i]==nums[i-1])continue;
//             int left=i+1,right=nums.size()-1;
            
//             while(left<right)
//             {
//                 int sum=nums[left]+nums[right]+nums[i];    
//                 if(sum>0)
//                 {
//                     --right;
//                 }
//                 else if(sum<0)
//                 {
//                     ++left;
//                 }
                
//                 else
//                 {
//                     retvector.push_back({nums[i],nums[left],nums[right]});
//                     ++left;
//                     --right;
                    
//                     while(left<right&&nums[left]==nums[left+1])left++;
//                     while(left<right&&nums[right]==nums[right-1])right--;
//                 }
                
//             } 
//         }
//         return retvector;
//     }
// };


// class Solution
// {
// public:
//     vector<vector<int>> threeSum(vector<int>& nums)
//     {
//         vector<vector<int>> retvector;
//         sort(nums.begin(),nums.end());
//         for(int i=0;i<nums.size()-2;i++)
//         {
//             if(nums[i]>0)break;
//             if(i>0&&nums[i]==nums[i-1])continue;
//             int left=i+1,right=nums.size()-1;
//             while(left<right)
//             {
//                 int sum=nums[i]+nums[left]+nums[right];
//                 if(sum==0)
//                 {
//                     retvector.push_back({nums[i],nums[left],nums[right]});
//                     right--,left++;
//                     while(left<right&&nums[left]==nums[left+1])left++;
//                     while(left<right&&nums[right]==nums[right-1])right--;
//                 }
//                 else if(sum>0)right--;
//                 else left++;
//             }
//         }
//         return retvector;
//     }
// };
// int main()
// {
//     Solution s;
//     vector<int> v;
//     v.push_back(-1);
//     v.push_back(0);
//     v.push_back(1);
//     v.push_back(2);
//     v.push_back(-1);
//     v.push_back(-4);
//     auto it = s.threeSum(v);
//     for(auto& e:it)
//     {
//         for(auto s:e)
//         {
//             cout<<s<<" ";
//         }
//     }
//     cout<<endl;
// }
// #include <iostream>
// using namespace std;

// int main() 
// {
//     long long a,h,b,k;
//     scanf("%lld %lld %lld %lld",&a,&h,&b,&k);
//     bool duili=true,guang=true;
//     long long hurt=0;
//     while(duili&&guang)
//     {
//         h-=b;
//         k-=a;
//         if(h==0&&k==0)
//         {
//             hurt+=a+b;
//             break;
//         }
//         else if(h==0)
//         {
//             hurt+=a*10;
//             break;
//         }
//         else if(k==0)
//         {
//             hurt+=b*10;
//             break;
//         }
//         else hurt+=a+b;
//     }
//     printf("%lld",hurt);
//     return 0;
// }


// #include <iostream>
// #include <string>
// using namespace std;
// bool ishw(string s,int left,int right)
// {
//     for(int i=left,j=right;i<=right&&j>=left&&left<=right;i++,j--)
//     {
//         if(s[i]!=s[j])return false;
//     }
//     return true;
// }
// int main() 
// {
//     string s;
//     cin>>s;
//     int left=0,right=s.size()-1;
//     if(!ishw(s,left,right))cout<<s.size()<<endl;return 0;
//     if(ishw(s,left,right))cout<<0<<endl;return 0;
//     while(left<=right)
//     {
//         if(s[left]!=s[right])left++,right++;
//         else if(s[left]==s[right])
//         {
//             if(ishw(s,left,right))
//             {
//                 cout<<(left+1>s.size()-right+1?left+1:s.size()-right+1)<<endl;
//                 return 0;
//             }
//         }
//     }
//     return 0;
// }

// #include <iostream>
// #include <list>
// #include <vector>
// #include <queue>
// #include <stack>
// #include <algorithm>
// using namespace std;
// class Graph
// {

// };

// int main()
// {
//     return 0;
// }


// class People
// {
// public:
//     int father;
//     int mother;
//     People():father(-1),mother(-1)
//     {}
// }people[1000000];

// map<int,char> sex;
// int flag=0;
// void dfs(set<int>&s1,int id,int deepth)
// {
//     if(deepth>5)return;
//     if(s1.count(id)==1){flag=1;return;}
//     s1.insert(id);
//     if(people[id].father!=-1)
//         dfs(s1,people[id].father,deepth+1);
//     if(people[id].mother!=-1)
//         dfs(s1,people[id].mother,deepth+1);   
// }
// int main()
// {
//     int n;
//     cin>>n;
//     for(int i=1;i<=n;i++)
//     {
//         int id,fatherid,motherid;
//         char gender;
//         cin>>id>>gender>>fatherid>>motherid;
//         sex[id]=gender;
//         people[id].father=fatherid;
//         people[id].mother=motherid;
//         sex[fatherid]='M';
//         sex[motherid]='F';
//     }
//     int m;
//     cin>>m;
//     for(int i=1;i<=m;i++)
//     {
//         int fid,sid;
//         cin>>fid>>sid;
//         if(sex[fid]==sex[sid])cout<<"Never Mind"<<endl;
//         else
//         {
//             set<int> st2;
//             flag=0;
//             dfs(st2,fid,1);
//             dfs(st2,sid,1);
//             if(flag==0)cout<<"Yes"<<endl;
//             else cout<<"No"<<endl;
//         }
//     }
//     return 0;
// }
// #include <iostream>
// #include <unordered_map>
// #include <unordered_set>
// #include <vector>
// #include <string>
// #include <queue>
// #include <map>
// #include <set>
// using namespace std;
// // class People
// {
// public:
//     int f;
//     int m;
//     People():f(-1),m(-1)
//     {}
// };
// People people[100000];
// //标记是否由已存在的
// int flag=0;

// void dfs(set<int>& s,int id,int deepth)
// {
//     if(deepth>5)return;
//     if(s.count(id)==1)
//     {
//         flag=1;
//         return;
//     }
//     s.insert(id);
//     if(people[id].f!=-1)dfs(s,people[id].f,deepth+1);
//     if(people[id].m!=-1)dfs(s,people[id].m,deepth+1);
// }
// int main()
// {
//     //性别的映射
//     map<int,char> sex;
//     int n;
//     cin>>n;
//     for(int i=1;i<=n;i++)
//     {
//         int id,fid,sid;
//         char gender;
//         cin>>id>>gender>>fid>>sid;
//         sex[id]=gender;
//         people[id].f=fid;
//         people[id].m=sid;
//         sex[fid]='M';
//         sex[sid]='F';
//     }
//     int m;
//     cin>>m;
//     for(int i=1;i<=m;i++)
//     {
//         int fid,sid;
//         cin>>fid>>sid;
//         if(sex[fid]==sex[sid])cout<<"Never Mind"<<endl;
//         else
//         {
//             set<int> s;
//             flag=0;
//             dfs(s,fid,1);
//             dfs(s,sid,1);
//             if(flag==0)cout<<"Yes"<<endl;
//             else cout<<"No"<<endl;
//         }
//     }
//     return 0;
// }
// #include <iostream>
// #include <string>
// int sum(int _start,int _end)
// {
//     int result=0;
//     for(int i=_start;i<=_end;i++)
//     {
//         result+=i;
//     }
//     return result;
// }
// int main()
// {
//     int start=1,end=100;
//     std::cout<<"[start,end]的和为："<<sum(start,end)<<std::endl;
//     return 0;
// }

// int BF(string&a, string&b)
// {
//     int i=0,j=0;
//     while(i<=a.size()-b.size())
//     {
//         j=0;
//         while(j<b.size()&&a[i+j]==b[j])
//         {
//             j++;
//         }
//         if(j==b.size())return i;
//         ++i;
//     }
//     return -1;
// }
// int BF(string& a,string& b)
// {
//     size_t i=0,j=0;
//     while(i<a.size()&&j<b.size())
//     {
//         if(a[i]!=b[j])i++,j=0;
//         else i++,j++;
//         if(j==b.size())return i-j;
//     }
//     return -1;
// }
// int main()
// {
//     // string a("abed");
//     // string b("ed");
//     // cout<<BF(a,b)<<endl;
//     cout<<10%2<<endl;
// }

// #include <iostream>
// #include <cstdlib>
// using namespace std;
// typedef struct TreeNode *Tree;
// struct TreeNode
// {
//     int val;
//     Tree left;
//     Tree right;
//     int flag;
// };
// Tree BuyNode(int data)
// {
//     Tree T=(Tree)malloc(sizeof(struct TreeNode));
//     if(T==nullptr)exit(1);
//     T->left=T->right=nullptr;
//     T->val=data;
//     T->flag=0;
//     return T;
// }
// Tree insert(int data,Tree T)
// {
//     if(!T)T=BuyNode(data);
//     else{
//         if(T->val<data)T->right=insert(data,T->right);
//     else T->left=insert(data,T->left);
//     }
    
//     return T;
// }
// Tree BuildTree(int n)
// {
//     Tree T;
//     int data;
//     cin>>data;
//     T=BuyNode(data);
//     for(int i=1;i<n;i++)
//     {
//         cin>>data;
//         T=insert(data,T);
//     }
//     return T;
// }
// int CheckTreeNode(int data,Tree T)
// {
//     if(T->flag)
//     {
//         if(T->val<data)return CheckTreeNode(data,T->right);
//         else if(T->val>data)return CheckTreeNode(data,T->left);
//         else return 0;
//     }
//     else
//     {
//         if(T->val==data)
//         {
//             T->flag=1;
//             return 1;
//         }
//         else return 0;
//     }

// }
// int Judge(int n,Tree T)
// {
//     int data,flag=0;
//     cin>>data;
//     if(T->val!=data)flag=1;
//     else T->flag=1;
//     for(int i=1;i<n;i++)
//     {
//         cin>>data;
//         if(!flag&&!CheckTreeNode(data,T))flag=1;
//     }
//     if(flag)return 0;
//     else return 1;
// }
// void reflag(Tree T)
// {
//     if(T->left)reflag(T->left);
//     if(T->right)reflag(T->right);
//     T->flag=0;
// }
// void destory(Tree T)
// {
//     if(T->left)destory(T->left);
//     if(T->right)destory(T->right);
//     free(T);
// }
// int main()
// {
//     int N,L;
//     cin>>N;
//     Tree T;
//     while(N)
//     {
//         cin>>L;
//         T=BuildTree(N);
//         for(int i=0;i<L;i++)
//         {
//             if(Judge(N,T))cout<<"Yes"<<endl;
//             else cout<<"No"<<endl;
//             reflag(T);
//         }
//         destory(T);
//         cin>>N;
//     }
    
//     return 0;
// }
// #include <iostream>
// #include <queue>
// #include <vector>
// using namespace std;

// typedef struct TreeNode *Tree;
// struct TreeNode {
//     int val;
//     Tree left;
//     Tree right;
// };

// // 构建新节点
// Tree BuyNode(int data) {
//     Tree T = new TreeNode;
//     T->left = T->right = nullptr;
//     T->val = data;
//     return T;
// }

// // 插入节点
// Tree insert(int data, Tree T) {
//     if (!T) T = BuyNode(data);
//     else {
//         if (T->val > data) T->left = insert(data, T->left);
//         else T->right = insert(data, T->right);
//     }
//     return T;
// }

// // 层序遍历
// void levelOrderTraversal(Tree T, vector<int>& result) {
//     if (!T) return;
//     queue<Tree> q;
//     q.push(T);
//     while (!q.empty()) {
//         Tree node = q.front();
//         q.pop();
//         result.push_back(node->val);
//         if (node->left) q.push(node->left);
//         if (node->right) q.push(node->right);
//     }
// }

// // 判断是否为完全二叉树
// bool isCompleteBinaryTree(Tree T) {
//     if (!T) return true;
//     queue<Tree> q;
//     q.push(T);
//     bool flag = false; // 标记是否遇到过空节点
//     while (!q.empty()) {
//         Tree node = q.front();
//         q.pop();
//         if (node == nullptr) {
//             flag = true;
//         } else {
//             if (flag) return false; // 如果遇到过空节点后再遇到非空节点，不是完全二叉树
//             q.push(node->left);
//             q.push(node->right);
//         }
//     }
//     return true;
// }

// // 构建二叉搜索树
// Tree BuildTree(int n) {
//     Tree T = nullptr;
//     for (int i = 0; i < n; i++) {
//         int data;
//         cin >> data;
//         T = insert(data, T);
//     }
//     return T;
// }

// int main() {
//     int N;
//     while (cin >> N && N != 0) {
//         Tree T = BuildTree(N);

//         vector<int> levelOrderResult;
//         levelOrderTraversal(T, levelOrderResult);

//         // 输出层序遍历结果
//         for (size_t i = 0; i < levelOrderResult.size(); ++i) {
//             if (i > 0) cout << " ";
//             cout << levelOrderResult[i];
//         }
//         cout << endl;

//         // 判断是否为完全二叉树
//         if (isCompleteBinaryTree(T)) {
//             cout << "YES" << endl;
//         } else {
//             cout << "NO" << endl;
//         }

//         // 清理内存
//         // 这里可以使用递归销毁树，但为了简洁，这里不做处理
//     }

//     return 0;
// }
// #include <iostream>
// #include <queue>
// #include <stack>
// #include <vector>
// using namespace std;
// //松针上的松树枝是一个相邻元素降序的队列
// //盒子初始为空
// //先从盒子里取，如果盒子为空，从推送器里取，
// //不满足要求就放到盒子里，接着去取推送器里的下一个
// //后一个插入的松枝不能比前一个大，小盒子满足，就取小盒子，否则推送器
// //如果推送器不满足要求就放到盒子里，接着去取推送器里的下一个
// //结束
// //1.小盒子满了，松针不满足要求，把盒子里的松针返回推送器，进行下一根
// //2.推送器没有松针了
// //3.松枝插满了

// int main()
// {
//     //推送器，小盒子，松枝干
//     int n,m,k;
//     cin>>n>>m>>k;
//     int a[n],c[k];//推送器的数组，松枝干的数组
//     for(int i=0;i<n;i++)cin>>a[i];
//     stack<int> q;//小盒子
//     vector<int> b;//正在插入的松枝
//     for(int i=0;i<n;i++)
//     {
//         //从盒子里取松针
//         while((!q.empty())&&(b.empty()||q.top()<=b.back()))
//         {
//             b.push_back(q.top());
//             q.pop();
//         }
//         //盒子为空，就从推送器取
//         if(b.empty()||a[i]<=b.back())
//         {
//             b.push_back(a[i]);
//         }
//         else
//         {
//             if(q.size()<m)q.push(a[i]);
//             else
//             {
//                 for(int j=0;j<b.size();j++)
//                 {
//                     if(j==b.size()-1)cout<<b[j]<<endl;
//                     else cout<<b[j]<<" ";
//                 }
//                 b.clear();
//                 --i;
//             }
//         }
//         if(b.size()==k||i==n-1)
//         {
//             for(int j=0;j<b.size();j++)
//             {
//                 if(j==b.size()-1)cout<<b[j]<<endl;
//                 else cout<<b[j]<<" ";
//             }
//             b.clear();
//         }
//         while(!q.empty())
//         {
//             if(b.empty()||q.top()<=b.back())
//             {
//                 b.push_back(q.top());
//                 q.pop();
//             }
//             else break;
//             if(b.size()==k)
//             {
//                 for(int j=0;j<b.size();j++)
//                 {
//                     if(j==b.size()-1)cout<<b[j]<<endl;
//                     else cout<<b[j]<<" ";
//                 }
//                 b.clear();
//             }
//         }
//     }
//     return 0;
// }
// #include <iostream>
// using namespace std;
// int get(int x)
// {
//     if(x<10)return 1;
//     else return get(x/10);
// }
// bool Getgigit(int x)
// {
//     int n=get(x),k;
//     int b[n];
//     for(int i=0;i<n;i++)
//     {
//         while(x)
//         {
//             k=x%10;
//             x/=10;
//             b[i]=k;
//         }
//     }
//     for(int i=0;i<n-1;i++)
//     {
//         if(b[i]!=b[i+1])return false;
//     }
//     return true;
// }

// int solution(int x, int y) {
//     // Edit your code here
//     int count=0;
//     for(int i=x;i<=y;i++)
//     {
//         if(Getgigit(i))count++;
//     }
//     return count;
// }

// int main() {
//     // Add your test cases here

//     std::cout << (solution(1, 10) == 9) << std::endl;
//     std::cout << (solution(2, 22) == 10) << std::endl;

//     return 0;
// }
// #include <iostream>
// #include <algorithm>
// #include <vector>
// #include <set>
#include <bits/stdc++.h>
using namespace std;
// int com(int a,int b){return a<b;}
// int main()
// {
//     vector<int> a({9,9,1,1,2,3,4,4,5,5});
//     vector<int> arr{1,2,2,6,5,5,4,8};//1,2,3,4,5,5,6,8
//     sort(arr.begin(),arr.end());
//     //查看排序后的数组的第i个元素的值，可能会将数组排好序，或者i左边比i小，右边比i大
//     nth_element(a.begin(),a.begin()+1,a.end());
//     //排序好的数组去重(unique)，使用前必须排好序，否则出现错误
//     // int newlength=unique(a.begin(),a.end())-a.begin();
//     // for(auto s:a)
//     // {
//     //     cout<<s<<" ";
//     // }
//     // cout<<endl;
//     // cout<<newlength<<endl;
    
//     //二分查找一个有序数组里是否存在某个元素
//     // bool isexist=binary_search(a.begin(),a.end(),4);
//     // cout<<isexist<<endl;

//     //返回一个数字可以在有序的数组里插入的位置区间
//     // int rightpos=upper_bound(arr.begin(),arr.end(),5)-arr.begin();//插入的右区间
//     // int leftpos=lower_bound(arr.begin(),arr.end(),5)-arr.begin();//插入的左区间
//     // cout<<firstpos<<" "<<lastpos<<endl;

//     set<int> se;
//     // cout<<se[0]<<" "<<se[1]<<endl;
//     se.insert(3);
//     se.insert(4);
//     se.insert(5);
//     se.insert(6);
//     // for(int i=0;i<se.size();i++)cout<<se[i]<<" ";
//     // set<int>::iterator sit;
//     // for(set<int>::iterator it=se.begin();it!=se.end();)
//     // {
//     //     if(*it==4){
//     //         it=se.erase(it);
//     //     }
//     //     else
//     //     {
//     //         cout<<*it<<" ";
//     //         it++;
//     //     }
//     // }
//     set<int>::iterator sit;
//     for(set<int>::iterator it=se.begin();it!=se.end();it++)
//     {
//         if(*it==4){sit=se.erase(it);it=sit++;}
        
//         cout<<*it<<" ";
//     }
// }

// 1.初始化数组
// 2.计算取余
// 3.移动元素位置
// 4.减小数组大小
void joesph(int m,int n)
{
    int a[100],k=0,p=0;
    for(int i=0;i<m;i++)a[i]=i+1;
    while(m>1)
    {
        p=(p+n-1)%m;
        cout<<"第"<<++k<<"个出局的人是"<<a[p]<<endl;
        if(p<m-1)for(int i=p+1;i<m;i++)a[i-1]=a[i];
        m--;
    }
    cout<<"最后剩下的是"<<a[p]<<endl;
}
// int query(int k)
// {
//     double sum=0;
//     for(int i=1;;i++)
//     {
//         sum+=1.0/i;
//         if(sum>k)return i;
//     }
//     return -1;
// }
// int main()
// {
//     // int m,n;
//     // cin>>m>>n;
//     // joesph(m,n);
//     cout<<(1<<19)<<endl;
//     return 0;
// }

// #include <iostream>
// #include <algorithm>
// #include <vector>
// #include <cstring>
// using namespace std;
// int main()
// {
//     vector<int> v1,v2,v3;
//     int m,n;
//     while(cin>>m)
//     {
//         if(m<0)break;
//         v1.push_back(m);
//     }
//     while(cin>>n)
//     {
//         if(n<0)break;
//         v2.push_back(n);
//     }
//     size_t left=0,right=0;
//     while(left<v1.size()&&right<v2.size())
//     {
//         if(v1[left]==v2[right])
//         {
//             v3.push_back(v1[left]);
//             left++,right++;
//         }
//         else if(v1[left]<v2[right])left++;
//         else right++;
//     }
//     if(v3.empty()){cout<<"NULL";return 0;}
//     for(int i=0;i<v3.size();i++)
//     {
//         if(i==v3.size()-1)cout<<v3[i];
//         else cout<<v3[i]<<" ";
//     }
//     return 0;
// }
#include <iostream>
using namespace std;
// int main()
// {
//     int m,n;
//     cin>>m>>n;
//     vector<int> v1(m),v2;
//     for(int i=0;i<m;i++)v1[i]=i+1;
//     int index=0;
//     while(!v1.empty())
//     {
//         index=(index+n-1)%v1.size();
//         v2.push_back(v1[index]);
//         v1.erase(v1.begin()+index);
//         if(v1.empty())break;
//     }
//     for(int i=0;i<v2.size();i++)
//     {
//         if(i==v2.size()-1)cout<<v2[i];
//         cout<<v2[i]<<" ";
//     }
//     cout<<endl;
//     return 0;
// }
// #include <stdio.h>  

// // 函数：交换数组中两个元素  
// void swap(int* a, int* b) {  
//     int temp = *a;  
//     *a = *b;  
//     *b = temp;  
// }  

// // 函数：分区操作，返回基准元素的最终位置  
// int partition(int arr[], int low, int high) {  
//     int pivot = arr[high]; // 选择数组的最后一个元素作为基准  
//     int i = (low - 1); // 小于基准元素的区域边界  

//     for (int j = low; j < high; j++) {  
//         // 如果当前元素小于或等于基准  
//         if (arr[j] <= pivot) {  
//             i++; // 增加小于基准元素的区域边界  
//             swap(&arr[i], &arr[j]); // 交换元素  
//         }  
//     }  
//     swap(&arr[i + 1], &arr[high]); // 将基准元素放到正确的位置  
//     return (i + 1);  
// }  

// // 函数：快速排序算法  
// void quickSort(int arr[], int low, int high) {  
//     if (low < high) {  
//         int pi = partition(arr, low, high); // 获取分区索引  
//         // 递归排序分区  
//         quickSort(arr, low, pi - 1); // 排序基准左侧  
//         quickSort(arr, pi + 1, high); // 排序基准右侧  
//     }  
// }  

// // 函数：打印数组  
// void printArray(int arr[], int size) {  
//     for (int i = 0; i < size; i++) {  
//         printf("%d ", arr[i]);  
//     }  
//     printf("\n");  
// }  

// // 主函数  
// int main() {  
//     int arr[] = {46,79,56,38,40,84};  
//     int n = sizeof(arr) / sizeof(arr[0]);  
//     printf("原始数组: ");  
//     printArray(arr, n);  

//     quickSort(arr, 0, n - 1);  
    
//     printf("排序后数组: ");  
//     printArray(arr, n);  
//     return 0;  
// }



